package com.lwt.codetop.dp;
//121. 买卖股票的最佳时机

/**
 * 思路一：状态dp ---> 本题只能持有一只股票进行买卖
 *        状态表示：f[i][0/1]
 *         f[i][0]：表示第i天不持有股票的利润的所有集合方案
 *         f[i][1]：表示第i天持有股票的利润的所有集合方案
 *         属性：max
 *         初始化 f[0][0] = 0 f[0][1] = -prices[0]
 *         状态转移：看代码
 *         结果：f[n - 1][0]
 *
 * 思路二：贪心 + 前后缀最值处理：我们要使得利益最大化，那么买入的时候要尽可能的小，卖出的的话收益就会越多。
 *        为此，维护一个前缀最小值，遍历卖出点，不断更新答案即可
 */
public class BestTimeToBuyAndSellStock {
    public static void main(String[] args) {
        // 构建测试用例
        int[] prices = {7,1,5,3,6,4};
        int res = maxProfit1(prices);
//        int res = maxProfit2(prices);
        System.out.println(res);
    }

    /**
     * 思路一：状态dp
     * @param prices
     * @return
     */
    private static int maxProfit1(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 10][2];
        f[0][0] = 0;
        f[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            // 未持有股票：之前没有/之前有但今天卖出
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]); // 因为只有一股，买入的利润是负数
            // 持有：之前就有/之前没有但今天买入
            f[i][1] = Math.max(f[i - 1][1], -prices[i]);
        }
        return f[n - 1][0];
    }

    /**
     * 思路二：贪心 + 前缀最值处理
     * @param prices
     * @return
     */
    private static int maxProfit2(int[] prices) {
        int preMin = prices[0];
        int res = 0;
        for (int x : prices) {
            res = Math.max(res, x - preMin);
            preMin = Math.min(preMin, x);
        }
        return res;
    }
}
